#include<iostream>
#include<vector>
using namespace std;

//class A {
//public:
//	void test(float a)
//	{
//		cout << a;
//	}
//};
//class B : public A {
//public:
//	void test(int b) {
//		cout << b;
//	}
//};
//void main()
//{
//	A* a = new A;
//	B* b = new B;
//	a = b;
//	a->test(1.1);
//}
//class A {
//public:
//	A()
//		:m_val(0) 
//	{
//		test();
//	}
//	virtual void func() { cout << m_val; }
//	void test() { func(); }
//public:
//	int m_val;
//};
//class B :public A{
//public:
//	B() { test(); }
//	virtual void func() {
//		++m_val;
//		cout << m_val;
//	}
//};
//int main()
//{
//////	A* p = new B;
//	p->test();
//	return 0;
//}
//class Solution {
//public:
//    string minWindow(string s, string t) {
//        int hash1[128] = { 0 };
//        int hash2[128] = { 0 };
//        int kinds = 0;
//        for (char c : t)
//        {
//            if (hash1[c]++ == 0) kinds++;
//        }
//        int minlen = INT_MAX, begin = -1;
//        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
//        {
//            char in = s[right];
//            if (++hash2[in] == hash1[in]) count++;
//            while (count == kinds)
//            {
//                if (right - left + 1 < minlen)
//                {
//                    minlen = right - left + 1;
//                    begin = left;
//                }
//                char out = s[left++];
//                if (hash2[out]-- == hash1[out]) count--;
//            }
//
//        }
//        if (begin == -1)
//        {
//            return "";
//        }
//        else return s.substr(begin, minlen);
//    }
//};
class Solution {
public:
    vector<int> ret;
    vector<int> tmp;
    vector<int> index;
    vector<int> myindex;
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n), tmp.resize(n), index.resize(n), myindex.resize(n);
        for (int i = 0; i < n; i++)
        {
            index[i] = i;
        }
        mergeSort(nums, 0, n - 1);
        return ret;
    }
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int mid = (right + left) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = left;
        while (cur1 <= mid && cur2 <= right)
        {
            if (nums[cur1] > nums[cur2])
            {
                ret[index[cur1]] += right - cur2 + 1;
                tmp[i] = nums[cur1];
                myindex[i++] = index[cur1++];
            }
            else
            {
                tmp[i] = nums[cur2];
                myindex[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid)
        {
            tmp[i] = nums[cur1];
            myindex[i++] = index[cur1++];
        }
        while (cur2 <= right)
        {
            tmp[i] = nums[cur2];
            myindex[i++] = nums[cur2++];
        }
        for (int i = left; i <= right; i++)
        {
            nums[i] = tmp[i - left];
            index[i] = myindex[i - left];
        }
    }
};
int main()
{
    Solution sol;
    vector<int> nums { 5,2,6,1 };
    sol.countSmaller(nums);
    return 0;
}